The present invention relates to a turbo coder implementation, and in particular the present invention relates to a parallelization of a turbo coder implementation.
The base band part of a transmitter in a telecommunication system usually includes together with other parts a general encoder for bits to be transmitted. The encoder adds redundant information to an incoming data stream with bit size K. Thereby, the number of bits is increased by a factor of 1/r, depending on the coder rate r. Currently, coder rates of xc2xd and ⅓ are commonly used, although other rates are possible as well. As result for each block of K uncoded bits the encoder outputs a block of K/r coded bits.
At a receiving side for the data stream in the telecommunication system the original data stream is recalculated from the coded data block in a receiver even in case some bits get corrupted during transmission over, e.g., the air interface.
Recently, turbo coders have been introduced for the purpose of error control for the transmission of telecommunication data. In general, turbo coding involves applying two or more component codes to different interleaved versions of the same information sequence prior to transmission. As turbo coding is well known in the art, e.g., Berrou et al., xe2x80x9cNear Shannon Limit Errorxe2x80x94Correcting Coder and Decoder: Turbo-Codesxe2x80x9d, IEEE International Communication Conference, pp. 1064-1070, May 1993 and Sklar, xe2x80x9cA Primer on Turbo Code Conceptsxe2x80x9d, IEEE Communications Magazine, pp. 94-102, December 1997, no further details will be given here and the stated references are incorporated herein by reference.
An example for a turbo coder is shown in FIG. 8. As shown in FIG. 8, the turbo encoder consists of two turbo coder blocks TCB1, TCB2 being identical in structure. The difference for the two turbo coder blocks is that one receives the bits of the input block in an unchanged order, whereas the other receives the input bits in an interleaved order. For each input bit, e.g., three output bits are generated at the output 0, 1, and 2, respectively.
As shown in FIG. 8, the turbo coder block TCB1 comprises a first XOR gate 100 at its input and a second XOR gate 102 at its output. In between there are arranged three delay units 104 to 108 for the delay of the respective input bits. Similarly, the turbo coder block TCB2 comprises a third XOR gate 110 at its input and a fourth XOR gate 112 at its output. In between, there are provided three delay units 114 to 118 that delay the respective input bits.
As also shown in FIG. 8, the input signal to the turbo coder is supplied directly to the turbo coder block 1 while it is supplied via an interleaver 120 to the second turbo coder block TCB2. For the output 0 the input signal is also directly forwarded without any modification.
Operatively, parameters for the turbo coder shown in FIG. 8 are the number of delay units in each turbo coder block and further the supply of input signals to the different XOR gates 100, 102, 110, and 112.
A straightforward implementation of the turbo coder shown in FIG. 8 relies on the use of delay units as well as input and output registers (not shown in FIG. 8) such that turbo coding is done in a bitwise manner. Here, all delay units work with the same system clock so that the output of a delay unit represents the input thereof at the previous clock cycle.
While the straightforward implementation of the turbo coder using the delay units in a serial manner does not require many registers and XOR gates the main disadvantage is that turbo coding is executed in a serial way. This means that only one bit is coded per cycle of the system clock. In conclusion, for cases where high bit rates are necessary, the system clock frequency is to be increased to very high values.
If, e.g., 1200 channels are to be encoded each being related to a voice channel with 100 bits in a time period of 1 msec, the necessary system clock frequency is 120 Mhz.
Here, it would be very difficult to implement a related turbo coder, e.g., using ASIC or FPGA technology.
While one solution would be to implement a dedicated turbo coder for each channel, this would require a complicated handling of input and output bit streams since different channels still must be coded in parallel. This would lead to a very complex control logic to supply the right input at the correct time to the right turbo coder. Further, the outputs of the different turbo coders also would have to be handled in the same complicated way.
In view of the above, the object of the invention is to increase the processing speed of turbo coder blocks.
According to the present invention this object is achieved through a parallel realization of turbo coders.
Heretofore, the structure of a turbo coder block is initially described using a general formalized description which then forms the basis for a parallelization of the turbo coder block.
In particular, input samples to the turbo coder block are interpreted as elements of a parallel input vector of dimension n, where n is the degree of parallelization.
The general formalized description of the turbo coder block is then used to derive a mapping of this parallel input vector into at least one parallel output vector.
In more detail, an internal state variable substitution process is applied to each internal state variable of the general formalized description wherein the representation of the internal state variables is scanned for maximum time index elements which are then substituted through carrying out backward time index transitions using previously determined time index substituted representations of the internal state variables. These substitution steps are repeated until the representation of each internal state variable is only dependent on input vector elements and values for internal state variables of the turbo coder being delayed according to the degree of parallelization.
Further, the substitution process is carried out as well for each element of each parallel output vector. Again the representation of each vector element in each output vector is scanned for internal state variables having maximum time index and then a backward time index transition in the representation of the vector element is determined recursively until the representation of the vector element is only dependent on input vector elements and values for internal state variables being delayed according to the degree of parallelization.
Therefore, only one parallelized turbo coder block is necessary instead of many serial turbo coders to achieve an increased processing speed. This leads to the decisive advantage that no complicated input and output control for a plurality of turbo coder blocks is necessary.
E.g., for a four bit parallel turbo coder block the resulting system clock frequency in the example mentioned above lies in the range of 30 MHz and therefore may be easily realized using FPGA or ASIC technology. Therefore, the parallelized turbo coder blocks and the turbo coder derived therefrom achieve a speed-up over the serial turbo coder according to the degree of parallelization so that pre-defined specification may be met using FPGA or ASIC technology-based implementations. Thus, the parallelized turbo coder block may form the basis for complicated telecommunication systems having low processing delay in the base band part without complicated handling of different channels at the same time.
Further, the parallelized turbo coder block and related turbo coder require only a minimum additional surplus in logic gates and registers when being compared to the serial turbo coder.
Still further, when processing blocks in front and subsequent to the turbo coder also support a parallel processing manner, the complete encoder block in total requires less logic and registers than the encoder block with a serial turbo coder and some additional converters (parallel to serial and vice versa).
According to another preferred embodiment, a computer program product is stored in a computer memory and includes software code portions for performing the steps according to the inventive parallelization method when being run on a computer. Preferably, the software code portions are of the VHDL type.
The present invention permits fast development and modification of parallel turbo coder design with decreased number of development cycles and increased flexibility with respect to the mapping of the design to different hardware technologies, e.g., ASIC or FPGA, respectively.